/**
 * This is an implementation of the stack structure using linked lists.
 *
 * @param <T> the type of elements in the stack
 */

public class MyLLStack<T> implements MyStack<T>
{
	
	// The top of the stack, i.e. the head node of the linked list
	private Node<T> top;
	
	public MyLLStack()
	{
		top = null;
		//throw new RuntimeException("You must implement this method!");
	}

	public void push(T element)
	{
		// setup a new node 
		Node<T> tmp = new Node<T>(element, top);
		// insert the node at the front
		top = tmp;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public T pop()
	{
		// check the stack status to avoid nullpointer exception
		if (isEmpty()){
			return null;
		}
		
		Node<T> tmp = top;
		// delete the node from the linklist
		top = tmp.getNext();
		
		return tmp.getData();
		//throw new RuntimeException("You must implement this method!");
	}
	
	public boolean contains(T element)
	{
		// check the status of the stact 
		if (isEmpty()){
			return false;
		}
		
		// traverse the linklist to findout the specific element
		Node<T> tmp = top;
		while (tmp != null){
			if (tmp.getData().equals(element)){
				return true;
			}
			tmp  = tmp.getNext();
		}
		
		// go through all the list but no equal element found?
		return false;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public boolean isEmpty()
	{
		if (top == null){
			return true;
		}
		else{
			return false;
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
}
